int* process(vector<int>& nums,int left,int right,int pivot)
{
    int cur = left; 
    int less = left-1;
    int more = right+1;
    while(cur < more)
    {
        if(nums[cur] > pivot)
            ::swap(nums[cur],nums[--more]);
        else if(nums[cur] < pivot)
            ::swap(nums[cur++],nums[++less]);
        else 
            cur++;
    }
    return new int[2]{less+1,more-1};
}
void QuickSort(vector<int>& nums,int left,int right)
{
    if(left >= right)
        return ;
    ::swap(nums[right],nums[left + rand() % (right - left + 1)]); //left-right
    int* equal = process(nums,left,right,nums[right]);
    //[left,equal[0] -1] [equal[1]+1,right]
    QuickSort(nums,left,equal[0]-1);
    QuickSort(nums,equal[1]+1,right);
}